package search;

/*
    二分查找的非递归实现
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] array = new int[]{1,3,5,6,7,8,9,15};

        for (int i : array) {
            System.out.println(binarySearch(array, i));
        }
    }

    public static int binarySearch(int[] array, int target) {
        int len = array.length;
        int leftIndex = 0, rightIndex = len - 1;
        int mid = 0;

        while (leftIndex < rightIndex) {
            mid = leftIndex + (rightIndex - leftIndex) / 2;
            if (array[mid] == target) {
                return mid;
            }
            if (array[mid] < target) {
                leftIndex = mid+1;
                continue;
            }
            if (array[mid] > target) {
                rightIndex = mid-1;
                continue;
            }
        }

        // 那么就是 array[mid] == target
        return leftIndex;

    }
}
